\begin{abstract}

A test must be effective at detecting defects, but it must be easy
to understand. A test that finds no defects is useless for testing.
However, a defect-revealing test that 
requires substantial comprehension effort is less useful
in practice. Recently, a number of techniques have been developed
to automatically generate new tests; however, there are few
solutions to simplify an existing test to assist programmers
in understanding its behavior.

In this paper, we show that existing syntax-level test simplification
techniques are fundamentally insufficient, and present
a new semantic-level test simplification
technique. We first formalize the \textit{semantic test simplification} problem,
and prove it is NP-hard. Then, we propose a heuristic algorithm,
\SimpleTest, that automatically transforms a test into an
easier-to-understand simplified test, while still preserving a
given property $\phi$. The key insight of \SimpleTest is to
\textit{reconstruct} a simple executable test that exhibits
$\phi$ from the original one. Although \SimpleTest cannot
guarantee optimal simplification, we empirically show that it
often generates optimally simplified tests on 7 real-world
programs with up to 150KLOC. We further
applied \SimpleTest to the application domain of automated
debugging, and demonstrated that semantically simplified tests
are useful in improving two existing automated debugging techniques.


\end{abstract}
